#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=35 lang=cpp
 *
 * [35] 搜索插入位置
 */

// @lc code=start
class Solution {
public:
    // int searchInsert(vector<int>& nums, int target) {
    //     // []
    //     int l = 0, u = nums.size() - 1;
    //     while (l <= u) {
    //         int middle = (l + u) / 2;
    //         if (nums[middle] < target) l = middle + 1;
    //         else u = middle - 1;
    //     }
    //     return l;
    // }

    int searchInsert(vector<int>& nums, int target) {
        // ( ] 第一个 >= target
        int l = -1, u = nums.size();
        while (u - l > 1) {
            int middle = (l + u) / 2;
            if (nums[middle] < target) l = middle;
            else u = middle;
        }
        return u;
    }
};
// @lc code=end

